/**
* Copyrights 2011 Michal Saman, m.saman@designplus.cz.
* This source code is release under the Apache License 2.0.
* http://www.apache.org/licenses/LICENSE-2.0
*
* @file	 queue.c
* @brief Implementation for circular queue operations (inserting, creating, deleting)
*/


#include <env.h>
#include <stdint.h>
#include <mem/kheap.h>
#include <lib/queue.h>

/**
 * Add item to circular queue.
 * If queue is NULL then creates new circular queue and add item to it.
 * @param 	item 	Item to add.
 * @param 	queue Pointer to existing queue to which item will be inserted, NULL to create new queue.
 * @return 	true if ok, false if not iserted (error)
 */
bool queue_insert(type_t* item, queue_t** queue) {
	if (queue==NULL) return false;

	queue_t *q = (queue_t*)kmalloc(sizeof(queue_t));
	if (q==NULL) return false;

	q->item = item;

	if (*queue == NULL) {
		q->next = q;
		*queue = q;
	} else {
		q->next = (*queue)->next;	// connect current item to new item
		(*queue)->next = q;		// connect new item to chain
	}
	return true;
}

/**
 * Remove item from circular queue.
 * @param 	item 	Item to remove from queue
 * @param 	queue Pointer to existing queue from which item will be removed.
 * @return 	true: if item exist and was removed or item not found if queue or queue not exists, false: if queue exists, item exist in queue and can't be removed.
 */
bool queue_delete(type_t* item, queue_t** queue) {
	if (queue==NULL) return true;
	if (*queue==NULL) return true;

	queue_t* q2 = NULL;
	queue_t* q = *queue;

	do {
		q2 = q;										// backup current item
		q = q->next;								// move to next item
		if (q->item == item) {						// check for analogy, if true we found item to delete
			q2->next = q->next;						// reconnect chain (skip deleted item)
			if (q == q->next && *queue==q) {		// queue has only one item
				*queue = NULL;						// queue is empty now
			} else {
				*queue = q2->next;
			}
			kfree(q);
			return true; // ok, item found and removed
		}
	} while(q != *queue);

	return true; // item not fount, never mind...
}

/**
 * Search for item in circular queue and returns first occurance of item.
 * @param 	item 	Item to find
 * @param 	queue 	Pointer to existing queue to search.
 */
type_t queue_lookup(type_t* item, queue_t* queue) {
	 if (queue==NULL) return NULL;

	queue_t* q = queue;

	do {
		if (q->item == item) {						// check for analogy, if true we found item to delete
			return q->item; 						// ok, item found, return it
		}
		q = q->next;								// move to next item
	} while(q != queue);

	return NULL;									// item not found
}

/**
 * Pickup current item from queue and move pointer to next item.
 * @param 	queue	 	Pointer to queue
 * @return 	item		Item from queue
 */
type_t queue_pop(queue_t** queue) {
	if (queue==NULL) return NULL;
	if (*queue==NULL) return NULL;

	queue_t* q = *queue;			// backup current pointer to queue
	*queue = q->next;				// move pointer to next item
	return q->item;					// return current item

}

/**
 * Count items in queue.
 * @param 	queue	 	Pointer to queue
 * @return 	item		Count of items in queue
 */
uint32_t queue_count(queue_t* queue) {
	if (queue==NULL)
		return 0;

	uint32_t c = 0;

	queue_t* q = queue;

	do {
		c++;
		q = q->next;								// move to next item
	} while(q != queue);

	return c;
}

/**
 * Moves item from source queue to destination queue.
 * If destination queue is NULL than it's automatically created.
 * @param sq Pointer to source queue
 * @param dq Pointete to destination queue
 * @return true if moved, false is something fails
 */
bool queue_move(queue_t** sq, queue_t** dq) {
	return queue_insert((*sq)->item, dq) && queue_delete((*sq)->item, sq);
}
